class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 1:
            return s

        dp = [[0 for i in range(len(s))] for i in range(len(s))]
        #单个字符串为回文
        for i in range(0, len(s)):
            dp[i][i] = 1
        
        #长度为2的字符串
        max_str = s[0]
        for i in range(0, len(s) - 1):
            if s[i] == s[i+1]:
                dp[i][i+1] = 1
                max_str = s[i:i+2]

        for l in range(2, len(s)):
            for i in range(len(s) - l):
                if s[i] == s[i+l] and dp[i + 1][i + l - 1] == 1:
                    dp[i][i + l] = 1
                    max_str = s[i:i+l+1]
                else:
                    dp[i][i + l] = 0
        return max_str
